/**
 * 快速排序
 */

function swap(nums, i, j) {
    var t = nums[i]
    nums[i] = nums[j]
    nums[j] = t
}

function partition(nums, left, right) {
    var i = left + 1
    var j = right
    while (i <= j) {
        while (i <= j && nums[i] <= nums[left]) {++i}
        while (i <= j && nums[j] > nums[left]) {--j}
        if (i < j) {
            swap(nums, i, j)
        }
    }
    swap(nums, left, j)
    return j
}

function qsort(nums, left, right) {
    if (left >= right) {
        return
    }
    var mid = partition(nums, left, right)
    qsort(nums, left, mid - 1)
    qsort(nums, mid + 1, right)
}

var nums1 = [3, 2, 1, 5, 4, 6, 9, 7, 8]
qsort(nums1, 0, nums1.length() - 1)
println(nums1)

var nums2 = [2, 4, 3, 2, 5, 7]
qsort(nums2, 0, nums2.length() - 1)
println(nums2)
